<20, 23 | 12, 15>
| 表示 fence, <>表示头节点和尾节点
template <class Elem> class List {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool append(const Elem&) = 0;
virtual bool remove(Elem&) = 0;
virtual void setStart() = 0;
virtual void setEnd() = 0;
virtual void prev() = 0;
virtual void next() = 0;
virtual int leftLength() const = 0;
virtual int rightLength() const = 0;
virtual bool setPos(int pos) = 0;
virtual bool getValue(Elem&) const = 0;
virtual void print() const = 0;
};

template <class Elem> class AList : public List<Elem> {
private:
int maxSize; // Maximum size of list
int listSize; // Actual elem count
int fence; // Position of fence
Elem* listArray; // Array holding list
public:
AList(int size=DefaultListSize) {
maxSize = size;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
~AList() { delete [] listArray; }
void clear() {
delete [] listArray;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
void setStart() { fence = 0; }
void setEnd() { fence = listSize; }
void prev() { if (fence != 0) fence--; }
void next() { if (fence <= listSize) fence++; }
int leftLength() const { return fence; }
int rightLength() const { return listSize - fence; }
bool setPos(int pos) {
if ((pos >= 0) && (pos <= listSize))
fence = pos;
return (pos >= 0) && (pos <= listSize);
}
bool getValue(Elem& it) const {
if (rightLength() == 0) return false;
else {
it = listArray[fence]; return true;
}
}
bool insert(const Elem&);
bool append(const Elem&);
bool remove(Elem&);
};
| 操作 | 复杂度 |
|---|---|
| Append | \(O(1)\) |
| Find | \(O(n)\) |
| Delete | \(O(n)\) |
| GeitByIndex | \(O(1)\) |
| Insert | \(O(n)\) |

// Singly-linked list node
template <class Elem> class Link {
public:
Elem element; // Value for this node
Link * next; // Pointer to next node
Link(const Elem& elemval, Link* nextval =NULL){
element = elemval;
next = nextval;
}
Link(Link* nextval =NULL){ next = nextval; }
};
template <class Elem> class LList:public List<Elem> {
private:
Link<Elem>* head, tail, fence;
int leftcnt, int rightcnt;
void init() { // Initialization routine
fence = tail = head = new Link<Elem>;
leftcnt = rightcnt = 0;
}
void removeall() {//Return link nodes back to free store
while(head != NULL) {
fence = head;
head = head->next;
delete fence;
}
}
public:
LList(int size=DefaultListSize) { init(); }
~LList() { removeall(); } //Destructor
void clear() { removeall(); init(); }
bool insert(const Elem&);
bool append(const Elem&);
bool remove(Elem&);
void setStart() {
fence = head;
rightcnt += leftcnt;
leftcnt = 0;
}
void setEnd() {
fence = tail;
leftcnt += rightcnt;
rightcnt = 0;
}
void prev(); void next() {
// Don't move fence if right empty
if (fence != tail) {
fence = fence->next;
rightcnt--;
leftcnt++;
}
}
int leftLength() const { return leftcnt; }
int rightLength() const { return rightcnt; }
bool getValue(Elem& it) const {
if(rightLength() == 0) return false;
it = fence->next->element;
return true;
}
void print () const;
};
| 操作 | 复杂度 |
|---|---|
| Append | \(O(1)\) |
| Find | \(O(n)\) |
| Delete | \(O(n)\) |
| FindByIndex | \(O(n)\) |
| Insert | \(O(1)\) |
比起单向链表,多了一个前驱指针。其删除操作的时间复杂度降到了\(O(1)\), 代价是浪费了春初空间。
template <class Elem> class Link
{
private:
static Link<Elem> *freelist;
static unsigned long freelistCount;
public:
Elem element;
Link * next;
Link * prev;
Link(const Elem&, Link *prevp = nullptr, Link *nextp = nullptr);
Link(Link *prevp = nullptr, Link *nextp = nullptr);
void * operator new(size_t);
void operator delete(void *);
};
template <class Elem> class DLList : public List<Elem>
{
private:
Link<Elem> *head; // Point to list header
Link<Elem> *tail; // Pointer to last Elem in list
Link<Elem> *fence; // Last element on left side
unsigned long leftcnt;
unsigned long rightcnt;
void init();
void removeall();
bool expand(unsigned long);
static unsigned long freelistLimit;
public:
DLList(unsigned long size = DEFAULT_LIST_SIZE);
~DLList();
void clear();
bool insert(const Elem&);
bool append(const Elem&);
bool remove(Elem&);
void setStart() ;
void setEnd();
void prev();
void next();
unsigned long leftLength() const;
unsigned long rightLength() const;
bool setPos(unsigned long);
bool getValue(Elem&) const;
void print() const;
};
| 操作 | 复杂度 |
|---|---|
| Append | \(O(1)\) |
| Find | \(O(n)\) |
| Delete | \(O(1)\) |
| FindByIndex | \(O(n)\) |
| Insert | \(O(1)\) |
特性:先进先出
template <class Elem> class Stack {
public:
// Reinitialize the stack
virtual void clear() = 0;
// Push an element onto the top of the stack.
virtual bool push(const Elem&) = 0;
// Remove the element at the top of the stack.
virtual bool pop(Elem&) = 0;
// Get a copy of the top element in the stack v
irtual bool topValue(Elem&) const = 0;
// Return the number of elements in the stack.
virtual int length() const = 0;
};
可以基于数组也可以基于链表实现
| 操作 | 复杂度 |
|---|---|
| Append | \(O(1)\) |
| Find | - |
| Delete | \(O(1)\) |
| FindByIndex | - |
| Insert | - |
#include <stack>
#include <vector>
std::stack<Typename> Stack;
empty() 测试栈是否为空,为空返回true,否则返回false。
size() 返回栈中元素的个数
top() 返回栈顶元素(最后push进来的那个)的引用。
push(val) 压一个值到栈中,其值将被初始化为 val
pop() 将栈顶元素弹出,注意这个函数无返回值
emplace(Args..) emplace 功能上与 push相同。不过emplace更高效。
swap() swap将两个 stack的内容交换。这两个 stack的模板参数 T和 Container必须都相同。
特性:先进先出
| 操作 | 复杂度 |
|---|---|
| Append | \(O(1)\) |
| Find | - |
| Delete | \(O(1)\) |
| FindByIndex | - |
| Insert | - |
#include <queue>
#include <vector>
std::queue<Typename> Queue;
empty() 测试队是否为空,为空返回true,否则返回false。
size() 返回队中元素的个数
front() 访问队首
back() 访问队尾
push(val) 压一个值到队尾,其值将被初始化为 val
pop() 将队首元素弹出,注意这个函数无返回值
emplace(Args..) emplace 功能上与 push相同。不过emplace更高效。
swap() swap将两个 stack的内容交换。这两个 stack的模板参数 T和 Container必须
特性:两边都可以进出
| 操作 | 复杂度 |
|---|---|
| Append | \(O(1)\) |
| Find | - |
| Delete | \(O(1)\) |
| FindByIndex | - |
| Insert | - |
#include <deque>
#include <vector>
std::deque<Typename> Deque;
empty() 测试队是否为空,为空返回true,否则返回false。
size() 返回队中元素的个数
front() 访问队首
back() 访问队尾
push_front(val) 压一个值到队首,其值将被初始化为 val
push_back(val) 压一个值到队尾,其值将被初始化为 val
pop_front() 将队首元素弹出,注意这个函数无返回值
pop_back() 将队尾元素弹出,注意这个函数无返回值
emplace(Args..) emplace 功能上与 push相同。不过emplace更高效。
swap() swap将两个 stack的内容交换。这两个 stack的模板参数 T和 Container必须
erase()
clear()
insert()
at()
本质上是维护一个堆(Heap),使得每次出队的元素优先度最大
node
children
edge
parent
ancestor
descendant
path 长度定义为edge的数量,方向是从浅节点到深节点
depth 根节点的深度为0
height 最深的节点的深度+1
level
leaf node 没有children的node
internal node 有children的 node
subtree
满二叉树(Full binary tree): 所有的internal node都有两个节点

全二叉树(Complete binary tree):height - 1 层的节点都是满的

The number of leaves in a non-empty full binary tree is one more than the number of internal nodes
The number of null pointers in a non-empty tree is one more than the number of nodes in the tree.
template <typename E> class BinNode {
public:
// Return the node’s value
virtual E& val() = 0;
// Set the node’s value
virtual void setVal(const E&) = 0;
// Return the node’s left child
virtual BinNode* left() const = 0;
// Set the node’s left child
virtual void setLeft(BinNode*) = 0;
// Return the node’s right child
virtual BinNode* right() const = 0;
// Set the node’s right child
virtual void setRight(BinNode*) = 0;
// Return true if the node is a leaf, false otherwise
virtual bool isLeaf() = 0;
};

如图
顾名思义,一层一层遍历节点
FBGADICEH
先访问根节点,再访问子节点
FBADCEGIH
先访问左子树,再访问右子树,最后访问根节点
ACEDBHIGF
先访问左子树,再访问根节点,最后访问右子树
ABCDEFGHI
template <class Elem>
void preorder(BinNode<Elem>* subroot) {
if (subroot == NULL) return; // Empty
visit(subroot); // Perform some action
preorder(subroot->left());
preorder(subroot->right());
}
【施工中】
若规定根结点的层数为\(1\),则从根结点到第\(L\)层结点的路径长度为\(L-1\)。
| Letter | Freq | Code | Bit |
|---|---|---|---|
| C | 32 | 1110 | 4 |
| D | 42 | 101 | 3 |
| E | 120 | 0 | 1 |
| M | 24 | 11111 | 5 |
| K | 7 | 111101 | 6 |
| L | 42 | 110 | 3 |
| U | 37 | 100 | 3 |
| Z | 2 | 111100 | 6 |
对于输入的二进制码,借助已经生成的哈夫曼树(字典)解码(相当于搜索树)。成功解码一个字符后立刻开始下一个字符的解码
Example
Code for ‘DEED’:10100101
Decode for ‘1011001110111101’:DUCK
遍历所有内节点,然后交换每个节点的左右子树
只要完成遍历即可,不必苛求何种遍历
二叉搜索树有如下特征:
二叉搜索树在使用时要处理好Remove和Insert操作,他们的复杂度在平衡(理想)情况下都是\(O(\log n)\)

对于满二叉树(Full binary trees),使用‘ / 等符号表示叶节点和内部节点,如
A’B’/DC’E’G/F’HI
'代表有子结点,/代表空指针,无'代表无子结点
疑问:
该方法只能用于Full binary trees嘛
对于一般的二叉树,用/表示空链接(null links)
AB/D//CEG///FH//I//
堆可以分为小顶堆和大顶堆
小顶堆,小的元素在上;大顶堆,大的元素在上
堆的实质是一颗二叉树。该二叉树的每一个节点的左子节点都比右子节点小(或者大,取决于具体实现)
堆的另一个特性是它除了最深一层外,每一层都是满的。给予这个特性,我们可以用数组来表示一个堆。对于一个节点,我们这样定义他的parent,leftchild,rightchild
int leftchild(int pos) const { return 2*pos+1; }
int rightchild(int pos) const { return 2*pos+2; }
int parent(int pos) const { return (pos-1)/2; }
// This heap has a fixed size, it drops values when adding new ones
template <class Elem, class Comp>
class SlidingHeap{
private:
int size;
int n;
void shiftdown(int);
void swap(int pos1, int pos2);
public:
Elem * heap;
// constructors, must define the copy constructor because it need to be copy-passed to saveHeap() in order to print sentences in the order of hash values
SlidingHeap(int max){ n=0; size = max; heap = new Elem[max];}
SlidingHeap(const SlidingHeap& H) {
heap = new Elem[H.size];
size = H.size;
n = H.n;
for (int i = 0; i < size; i++) { heap[i] = H.heap[i]; }
}
SlidingHeap(){}
// destructor
~SlidingHeap(){ delete[] heap;}
// Besides insert(), the rest of the implementation is similar to the demo code
int heapsize() const;
bool isLeaf(int pos) const {return (pos>=n/2) && (pos<n); }
int leftchild(int pos) const { return 2*pos+1; }
int rightchild(int pos) const { return 2*pos+2; }
int parent(int pos) const { return (pos-1)/2; }
bool insert(const Elem&);
bool removemax(Elem&);
bool remove(int, Elem&);
void buildheap(){ for (int i=n/2-1; i>=0; i--) shiftdown(i); }
void print(){ for(int i=0; i<n; i++){ std::cout << " | " << heap[i]; } std::cout << " | \n";}
};
shiftdown()操作将位于堆顶的元素安置到合适的位置
template <class Elem, class Comp>
void SlidingHeap<Elem, Comp>::shiftdown(int pos){
while (!isLeaf(pos)) {
int j = leftchild(pos);
int rc = rightchild(pos);
if (rc<n and Comp::lt(heap[j], heap[rc])) j = rc;
if (!Comp::lt(heap[pos], heap[j])) return;
swap(pos,j);
pos = j;
}
}
insert()用于插入元素,做法是:
shiftup()template <class Elem, class Comp>
bool SlidingHeap<Elem, Comp>::insert(const Elem& val){
// if the heap is full, decide whether to drop the input or the top element.
if (n >= size) {
if (Comp::gt(heap[0],val)) {
heap[0] = val;
shiftdown(0);
return true;
} else {
return false;
}
}
int curr = n++;
heap[curr] = val;
while ((curr != 0) and (Comp::gt(heap[curr], heap[parent(curr)]))) {
swap(curr, parent(curr));
curr = parent(curr);
}
return false;
}
template <class Elem, class Comp>
bool SlidingHeap<Elem, Comp>::removemax(Elem& it){
if (n == 0) return false;
swap(0, --n);
if (n != 0) shiftdown(0);
it = heap[n];
return true;
}
建堆的复杂度为\(O(n)\)
bottom-up建堆。有1/2的元素向下比较了一次,有\(\frac{1}{4}\)的向下比较了两次,\(\frac{1}{8}\)的,向下比较了3次,......,\(\frac{1}{2^k}\)的向下比较了\(k\)次,其中\(\frac{1}{2^k} \leq 1\), k 约等于\(log(n)\)。于是就有总的比较量:
\(T = (\sum_{k=1}^{\log n} \frac{1}{2^k}\times n\)
令\(S = \sum_{k=1}^{\log n} \frac{1}{2^k}\)
\(\frac{1}{2}S = \sum_{k=1}^{\log n} \frac{1}{2^{k+1}} = \frac{1}{4} + \frac{1}{8}\times 2+ ··· + \frac{1}{2^{k+1}}\times k\)
\(S - \frac{1}{2}S = \frac{1}{2}S = \frac{1}{2} + \frac{1}{4} + ··· + \frac{1}{2^k}-\frac{1}{2^{k+1}} \times k\)
显然 \(S \leq 2\)
出堆的复杂度为\(O(\log n)\)
使用自定义结构的时候需要自己写一个比较类
哈希函数是一类泛函。它们接受特定的参数,输出一个整数。对于一个key-value键值对,我们可以计算出key对应的hash值,然后将value存储到相应的位置上。
// ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x = 0;
while (*str)
{
hash = (hash << 4) + (*str++);//hash左移4位,把当前字符ASCII存入hash低四位。
if ((x = hash & 0xF0000000L) != 0)
{
//如果最高的四位不为0,则说明字符多余7个,现在正在存第8个字符,如果不处理,再加下一个字符时,第一个字符会被移出,因此要有如下处理。
//该处理,如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位,否则会影响5-31位,因为C语言使用的算数移位
//因为1-4位刚刚存储了新加入到字符,所以不能>>28
hash ^= (x >> 24);
//上面这行代码并不会对X有影响,本身X和hash的高4位相同,下面这行代码&~即对28-31(高4位)位清零。
hash &= ~x;
}
}
//返回一个符号位为0的数,即丢弃最高位,以免函数外产生影响。(我们可以考虑,如果只有字符,符号位不可能为负)
return (hash & 0x7FFFFFFF);
}
Hash函数一直是人规定的。我们追求计算迅速,分布均匀(针对特定问题)的哈希函数。
哈希表是为了实现字典而出现的
哈希表试图让查找的时间复杂度达到\(O(1)\)
// The Dictionary abstract class. template <class Key, class Elem,
class KEComp, class EEComp> class Dictionary {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool remove(const Key&, Elem&) = 0;
virtual bool removeAny(Elem&) = 0;
virtual bool find(const Key&, Elem&) const = 0;
virtual int size() = 0;
};
Class hashdict : public Dictionary<Key, Elem, KEComp, EEComp>;
哈希表可能会冲突。\(H(k_1) = \beta = H(k_2)\)
Open hashing 可以解决这个问题:每个哈希表的项目都是一个桶(bin)
Bucket Hashing 有两个桶。当一个Hash table满了的时候,数据放在Overflow里。寻找的时候也是如此
Closed Hashing 把所有的记录都存在hash table里。当发生冲突的时候,我们根据某种方式找到新的位置。寻找的时候也是这样。这个过程叫做Probe。
线性探测(Linear Probing)只是简单地寻找下一个槽,为了避免循环探测,表必须始终保留一个非空的槽
改进的线性探测(Improved Linear Probing)跳过常数C个槽,最好让C和表长M互质。
Random Probing 实际上不可能实现。可以事先构建一系列伪随机数(Pseudo-random numbers)作为Prob的步长
也可以通过平方来探测如30,31,34,39,46...这样
可以用两种不同的函数求哈希值,当第一种出现冲突时,用第二种算出步长进行查找。
Example: Hash table of size M=101
删除哈希表的元素时必须要小心:对于存在移位(Probe)的表,有必要让后面的元素继续保持可用。
一个好方法是防止里程碑(Tombstone)来代替被删除的元素。
这是一个通用二叉树的结构
value、parent、child、sibling四个attribute。就像这样节点
// General tree node ADT
template <class Elem> class GTNode { public:
GTNode(const Elem&); // Constructor
~GTNode();
Elem value();
bool isLeaf();
GTNode* parent();
GTNode* leftmost_child();
// First child GTNode* right_sibling();
// Right sibling void setValue(Elem&);
// Set value void insert_first(GTNode<Elem>* n);
void insert_next(GTNode<Elem>* n);
void remove_first(); // Remove first child
};
树
// General tree
template <typename E> class GenTree {
private:
GTNode<E>* root; public:
void clear(); // Send all nodes to free store
GTNode<E>* root(); // Return the root of the tree
// Combine two subtrees
void newroot(E&, GTNode<E>*, GTNode<E>*);
void print(); // Print a tree
};
General Tree的遍历实现可以有很多种。比如先遍历子一层,再遍历父一层。每层的兄弟节点间都有指针相连,灵活性很高。
如果移除child、sibling,仍然可以利用parent这个属性组成一颗树

这样可以节约一些空间,代价是很难将整个树输出。
有些时候,我们希望通过Union操作将两个树合并在一起,一个简单的思路是:
find()find()我们还可以先判断A、B两树的规模,让规模小的树加入规模大的,从而保持总体的平衡。
Union操作的时间复杂度取决于find操作的时间复杂度。在没有路径压缩的情况下复杂度为\(O(n\log n)\)
在Union操作中,find()操作会耗去很多时间。该操作与树的路径深度息息相关
如果我们能再每次find()操作中对路径进行压缩,就能够节约很多时间,如:
Point * find(Point * p) {
while(not isRoot(*p)) {
p->parent = p->parent->parent;
p = p->parent;
}
return p;
}
因此,find()操作的时间复杂度近似\(O(1)\)
如果我们放宽parent的限制,从事实上让parent指针变为ancestor指针,我们就可以实现path compression(操作ancestor指针),并且能够轻松输出每棵树的成员(借助child sibling指针。
用 )表示子节点的结束
RAC)D)E))BF)))
这里用到R表示根结点
| 算法 | 平均 | 最坏 | 最好 | 空间 | 稳定性 | 复杂度 |
|---|---|---|---|---|---|---|
| Insertion Sort | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | Stable | Simple |
| Shell Sort | \(O(n^{1.5})\) | \(O(n^{1.5})\) | \(O(n^{1.5})\) | \(O(1)\) | UnStable | Complex |
| Bubble Sort | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | Stable | Simple |
| Quicksort | \(O(n\log n)\) | \(O(n^2)\) | \(O(n\log n)\) | \(O(\log n)\) | Unstable | Complex |
| Selection | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | UnStable | Simple |
| Heapsort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | \(O(1)\) | Unstable | Complex |
| Mergesort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n)\) | Stable | Complex |
| Radix SOrt | \(O(k(n+r))\) | \(O(k(n+r))\) | \(O(k(n+r))\) | \(O(n+r)\) | Stable | Complex |
从头开始,对于每个位置,从未排序的数据中选取最优的


| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n^2)\) |
| 最坏 | \(O(n^2)\) |
| 平均 | \(O(n^2)\) |
从头开始,将i+1项向前插入到合适的位置


template <class Elem, class Comp>
void inssort(Elem A[], int n) {
for (int i=1; i<n; i++)
for (int j=i; (j>0) &&(Comp::lt(A[j], A[j-1])); j--)
swap(A, j, j-1);
}
| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n)\) |
| 最坏 | \(O(n^2)\) |
| 平均 | \(O(n^2)\) |
空间复杂度为\(n\)
insertion sort 无法用链表Linked List优化
和冒泡排序类似,但是减少了交换次数


template <class Elem, class Comp>
void selsort(Elem A[], int n) {
for (int i=0; i<n-1; i++) {
int lowindex = i; // Remember its index
for (int j=n-1; j>i; j--) {// Find least
if (Comp::lt(A[j], A[lowindex])) {
lowindex = j; // Put it in place
}
}
swap(A, i, lowindex);
}
}
| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n^2)\) |
| 最坏 | \(O(n^2)\) |
| 平均 | \(O(n^2)\) |
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
希尔排序的基本思想是:
template <class Elem, class Comp>
void inssort2(Elem A[], int n, int incr) {
for (int i = incr; i <n ; i+=incr)
for (int j = i; (j >= incr) and (Comp::lt(A[j], A[j-incr])); j--)
swap(A, j, j-incr);
}
template <class Elem, class Comp>
void shellsort(Elem A[], int n) {
for (int i = n/2; i > 2; i/2) // For each incr
for (int j = 0; j< i; j++) // sort sublists
inssort2<ELem, Comp>(&A[j], n-j, i);
inssort2<Elem, Comp>(A,n,1)
}
将数据分成两组,排序后合并;不断重复改操作
template<class Elem,class Comp>
void mergesort(Elem A[], Elem temp[], int left, int right) {
int mid = (left + right) / 2;
if (left == right) return;
mergesort<Elem, Comp>(A, temp, left, mid);
mergesort<Elem, Comp>(A, temp, mid+1, right);
for (int i = left; i <= right; i++)
temp[i] = A[i];
int i1 = left; int i2 = mid + 1;
for (int curr = left; curr <= right; curr++) {
if (i1 == mid + 1)
A[curr] = temp[i2++];
else if (i2 > right)
A[curr] = temp[i1++];
else if (Comp::lt(temp[i1], temp[i2]))
A[curr] = temp[i1++];
else A[curr] = temp[i2++];
}
}
| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n\log n)\) |
| 最坏 | \(O(n\log n)\) |
| 平均 | \(O(n\log n)\) |
分而治之思想,参照pivot将数组分成两部分,一部分小于pivot,一部分大于pivot。然后重复着一操作
template <class Elem> int FindPivot(Elem A[], int i, int j) { return (i + j) / 2; }
// pivot is supposed to be located at the end i.e. position r by convention
template <class Elem, class Comp>
int Partition(Elem A[], int l, int r, Elem& pivot) {
--l;
do {
while (Comp::lt(A[++l], pivot));
while ((r != 0) && Comp::gt(A[--r], pivot));
swap(A, l, r);
} while (l < r);
swap(A, l, r);
return l;
}
// Initial call: QuickSort(array,0,n-1)
template <class Elem, class Comp>
void QuickSort(Elem A[], int i, int j) {
if (j <= i) return;
int pivotidx = FindPivot<Elem>(A, i, j);
swap(A, pivotidx, j); // Put the pivot at the end
int k = Partition<Elem, Comp>(A, i, j, A[j]);
swap(A, k, j);
QuickSort<Elem, Comp>(A, i, k - 1);
QuickSort<Elem, Comp>(A, k + 1, j);
}
template <class Elem, class Comp>
void QuickSortDepth(Elem A[], int i, int j, int depth) {
if (depth < 1) return;
if (j <= i) return;
int pivotidx = FindPivot<Elem>(A, i, j);
swap(A, pivotidx, j); // Put the pivot at the end
int k = Partition<Elem, Comp>(A, i, j, A[j]);
swap(A, k, j);
if (1 == depth) cout << "Pivot : " << A[k] << " ";
QuickSortDepth<Elem, Comp>(A, i, k - 1, depth - 1);
QuickSortDepth<Elem, Comp>(A, k + 1, j, depth - 1);
}
| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n\log n)\) |
| 最坏 | \(O(n^2)\) |
| 平均 | \(O(n\log n)\) |
堆/优先队列的特点是接受任意序列的输入,输出有序序列,利用这一特点可以很方便地实现排序
| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n\log n)\) |
| 最坏 | \(O(n\log n)\) |
| 平均 | \(O(n\log n)\) |
| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n+k)\) |
| 最坏 | \(O(n+k)\) |
| 平均 | \(O(n+k)\) |

| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(n + k)\) |
| 最坏 | \(O(n^2)\) |
| 平均 | \(O(n + k)\) |
template<class Elem>
void binsort(Elem A[], int n) {
List<Elem> B[MaxKeyValue];
Elem item;
for (i=0; i<n; i++) B[A[i]].append(A[i]);
for (i=0; i< MaxKeyValue; i++)
for (B[i].setStart(); B[i].getValue(item); B[i].next())
output(item);
}
计数排序和桶排序很像,它基于数字的不同位数的规律将数字分类:


template <class Elem, class Comp>
void radix(Elem A[], Elem B[], int n, int k, int r, int cnt[]) {
int j;
for (int i=0; rtok=1; i<k; i++, rtok*=r) {
for (j=0; j<r; j++) cnt[j] = 0;
for (j=0; j<n; j--) cnt[(A[j]/rtok)%r]++;
for (j=1; j<r; j++) cnt[j] = cnt[j-1] + cnt[j];
for (j=n-1; j>=0; j--) B[--cnt[(A[j]/rtok)%r]] = A[j];
for (j=0; j<n; j++) A[j]=B[j];
}
}
| 情况 | 时间复杂度 |
|---|---|
| 最好 | \(O(k(n+r))\) |
| 最坏 | \(O(k(n+r))\) |
| 平均 | \(O(k(n+r))\) |
定义、继承、重载、私有/公有方法、多态、构造、销毁、友元函数、重载、类指针